package com.vint.mi;


/**
 * 1. done, medium
 * 三个相邻的字符串为非法，求个数
 * f1表示未尾不同，f2表示未尾两数相同
 * 共三个公式，dp:
 * f(n) = f1(n) + f2(n)
 * f(n) = 3*f1(n-1)+2*f2(n-1)
 *      =  2*f(n-1) + f1(n-1)
 * f1(n)=2f(n-1)
 *
 * 所以：f(n)=2f(n-1)+2f(n-2)
 */
public class Mi69 {
    public static String solution(String line){
        int l = Integer.parseInt(line);
        //return Integer.toString(f(l));
        return Long.toString(f2(l));
    }

    //超时
    public static int f(int n){
        if(n==1)return 3;
        if(n==2)return 9;
        return 2*f(n-1) + 2*f(n-2);
    }

    public static long f2(int n){
        if(n==1)return 3;
        if(n==2)return 9;
        long ret = 0;
        long start1 = 3;
        long start2 = 9;
       for(int i = 3; i<=n; i++){
           ret = 2*(start1+start2);
           start1 = start2;
           start2 = ret;
       }
       return ret;
    }

    public static void main(String[] args) {
        System.out.println(solution("22"));
        System.out.println(solution("4"));
    }
}
